package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.lang.reflect.GenericArrayType;

/**
 * https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
 * 双指针方法
 * 通过
 *
 * @author yulongTian
 * @create 2024-05-25 17:02
 */
public class Test07 {
    public static void main(String[] args) {
//        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5}));
//        System.out.println(calculateWater(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}, 3, 7));
    }

    public static int trap(int[] height) {
        int res = 0;
        int mid = 0;
        for (int i = 0; i < height.length; i++) {
            if (height[i] >= height[mid]) {
                mid = i;
            }
        }
        // left -> mid
        int leftPoint = 0;
        int rightPoint = leftPoint + 1;
        while (leftPoint < mid) {
            while (height[rightPoint] < height[leftPoint]) {
                rightPoint++;
                if (rightPoint > mid) {
                    break;
                }
            }
            if (rightPoint > mid) {
                leftPoint++;
                continue;
            }
            res += calculateWater(height, leftPoint, rightPoint);
            leftPoint = rightPoint;
            rightPoint++;
        }
        // right -> mid
        rightPoint = height.length - 1;
        leftPoint = rightPoint - 1;
        while (rightPoint > mid) {
            while (height[rightPoint] > height[leftPoint]) {
                leftPoint--;
                if (leftPoint < mid) {
                    break;
                }
            }
            if (leftPoint < mid) {
                rightPoint--;
                continue;
            }
            res += calculateWater(height, rightPoint, leftPoint);
            rightPoint = leftPoint;
            leftPoint--;
        }


        return res;
    }

    public static int calculateWater(int[] height, int start, int end) {
        int should;
        if (start <= end) {
            int temp = 0;
            int tempIndex = 0;
            for (int i = start; i < end + 1; i++) {
                if (height[i] != 0 && i != end) {
                    temp = height[i];
                    tempIndex = i;
                    break;
                }
            }
            int min = Math.min(temp, height[end]);
            should = min * (end - tempIndex + 1);
            for (int i = start; i < end + 1; i++) {
                if (height[i] <= min) {
                    should -= height[i];
                } else {
                    should -= min;
                }
            }
        } else {
            int temp = 0;
            int tempIndex = 0;
            for (int i = start; i >= end; i--) {
                if (height[i] != 0 && i != end) {
                    temp = height[i];
                    tempIndex = i;
                    break;
                }
            }
            int min = Math.min(temp, height[end]);
            should = min * (tempIndex - end + 1);
            for (int i = start; i >= end; i--) {
                if (height[i] <= min) {
                    should -= height[i];
                } else {
                    should -= min;
                }
            }
        }

        return should;
    }

}
